package pro11_20.pro11;

import utils.binarytree.BinaryTree;
import utils.binarytree.TreeNode;

/**
 * @author yaohuaiying
 * @create 2018-02-08 13:35
 *
 * 第11题（树）
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。

读题
 题目很容易理解
思路
 不就是两个深度最深的两个叶子之间的距离么
 先找到第一深和第二深的叶子的
 好像不对 这两个叶子是同一个父亲不就是只有2的距离了 ？
 那就是找到最深的叶子 然后去 遍历到其他（无子结点）叶子的距离 得到最大的那个  在比较和 最深的叶子到根的距离 ？ ……
 2 好像不用先找最深的
 记录各个叶子到根的距离emmm 好像不行 不能鉴别这些叶子之间的关系 作废
 好吧 去问度娘看看
百度1
计算一个二叉树的最大距离有两个情况:
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
 结合我的想法
 如果这样说的话 其实有可能会AB情况 大小相同的 但是不影响题目的结果 按百度的说法就是找结点的左右最大深度 比较即可
 又要写二叉树 算了 抽一个通用的二叉树出来 这个树形打印是真的丑-、-
 **/
public class Main {
    static int maxlen = 0;
    public static void main(String[] args){
        BinaryTree binaryTree = BinaryTree.createBinaryTree(6);
        binaryTree.treePrint(2);
        getMaxLen(binaryTree.getRoot());
        System.out.print("maxLen" + maxlen);
    }

    /**
     * 这里其实只要思考一个node怎么算  （为什么跟求最大深度那么像！ -、-）
     *    a
     *   / \
     *  b   c
     *  先算a的左分支b的最大长度
     *  b下面两个空  直接返回0+1
     *  c一样 返回0+1
     *  然后 a 会返回 它自己的到叶子的最大长度给上一层 就是 1
     *  每次maxlen与 左右值比较
     * @param currentNode
     * @return
     */
    public static int getMaxLen(TreeNode currentNode){
        if(currentNode == null){
            return -1;
        }
        int leftlen = getMaxLen(currentNode.getLeft()) + 1;
        int rightlen = getMaxLen(currentNode.getRight()) + 1;
        if(maxlen < leftlen + rightlen) {
            maxlen = leftlen + rightlen;
        }
        return leftlen>rightlen ? leftlen:rightlen;
    }
}
